package LeetCode.leetcode;

/**
 * @author: leiwenkang
 * @date: 2020/6/25
 * @time: 11:20
 */
public class Test169多数元素 {
    public static void main(String[] args) {
        int[] nums = {3, 2, 3};
        System.out.println(majorityElement(nums));
    }

    public static int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int low = 0;
        int high = nums.length - 1;
        int mid = (low + high) / 2;
        while (low <= high) {
            int pos = partition(nums, low, high);
            if (pos == mid) {
                return nums[pos];
            } else if (pos < mid) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }
        return -1;
    }

    private static int partition(int[] nums, int low, int high) {
        int val = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= val) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= val) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = val;
        return low;
    }


}
